# -*- coding:utf-8 -*-
# 操作复杂度O(n*n)

states_needed = {"mt", "wa", "or", "id", "nv", "ut", "ca", "az"}
stations = {"kone": {"id", "nv", "ut"}, "ktwo": {"wa", "id", "mt"}, "kthree": {"or", "nv", "ca"}, "kfour": {"nv", "ut"},
            "kfive": {"ca", "az"}}

final_stations = set()

while states_needed:

    best_station = None
    states_covered = set()
    for k, v in stations.items():
        covered = states_needed & v
        if len(covered) > len(states_covered):
            best_station = k
            states_covered = covered
    states_needed -= states_covered
    final_stations.add(best_station)

print(final_stations)
